ALU

Arithmetic Logic Unit
處理器裡面的算術邏輯單元

需要ALU的指令

• add/sub
• and/or/nor
• slt(set on less than)

比較兩個暫存器的大小
用一個減法即可達成
因為只要知道減完的結果是正的數字或是負的數字就好

簡介

兩個input:32個bit所組合而成
output:一樣也是32個bit
ALUop:控制ALU執行不同運算
carry out:為了做加法運算

設計ALU

Design Trick 1 : divide and conquer

搞分化

有一些運算裡面
可以把它切開來切成1-bit來做
例如Boolean的運算

比方說and or not這些運算 都可以一個bit一個bit來處理
前面之前已經談過bitwise的operation

但有些情況其實我們不能夠一個bit一個bit對付它
例如加法
我們都知道加法其實是需要處理進位
也因此我們可以先把它拆成一個bit一個bit
然後再把它的進位 也就是carry拉在一起

如此一來把它們通通黏好之後
整個32bit的ALU就完成了

Design Trick 2 : solve part of the problem and extend

把一部分的問題解決掉然後去進一步的延伸

比如我們先做出and/or/add/sub後來再擴充slt/nor

加法/or/and 實現

Design Trick 3 : take pieces you know

組合成4 bits

減法 實現

被減數維持不變
把減數拿來取2's complement
再跟被減數相加

2's complement: 先把它轉成1's complement然後再加1

組合成4 bits

最低位元以及最高位元我們需要做一些額外的處理

最高位元

我們可能需要判斷這個減法或是這個加法有沒有發生overflow

最低位元

減法其實是透過我們對B這個數字讓它去取2's complement

實作:通過一個MUX讓它去選擇B或是B'
如果當它選擇的是B'，我們得到的是B的1's complement
最後一定要加1
現在問題是這個1要怎麼來呢

今天我們設計的MUX須要有一個select的信號去做選擇
這裡我們讓select信號為1的時候我們選出來的值是B'
因此當我們真的想要去做減法
而需要supply一個額外的1進去到最低位元的時候
就利用這邊我們所設計的select信號
而這個select信號我們就把它叫做Bnegate

nor 實現

方法一:

nor gate接到ALU裡面的MUX問題就解決了

方法二:

由DeMorgan's Law : 
A nor B 可以轉換成(not A) and (not B)

還記得我們曾經已經設計了一個B'為了做減法
既然如此 我們何不乾脆再設計一個A'
讓我們前面的這個MUX分別的去選到A'以及B' 
然後使用and gate就成功了

判斷Overflow

發生overflow的原因:
計算的結果
正的數字太大 負的數字太小
至於超過了我們可以表達的數字範圍

舉例:

有一個4個bit的binary number
表達的數字範圍就是-8到+7
1000 ~ 0111

兩個正的數字加起來得到一個負的數字
或是兩個負的數字加起來得到一個正的數字
這就是overflow

• 加法overflow討論

原因

正的數字的最高位元一定會為0
正的數字當做加法的時候
有一個carry進來了
MSB最高位元就會為1

思考

最高位元會不會有carry跑出去?
可想而知一定不會
因為這裡有兩個0
兩個0怎麼加都不可能能夠產生出carry

• 減法overflow討論

原因

可想而知最高位元都是1
因此它的carry out一定會是1

如果今天最高位元它的carry in是0的話
最後的output一定也會是0

Overflow結論

當Overflow發生:
最高位元的carry out是1 最低位元的carry in是0
或是
最高位元的carry out是0 最低位元的carry in是1

所以判斷這兩個bit只要不同就代表發生了Overflow

exclusive or gate 為1代表不同，也就是overflow發生

ALU zero

zero為1的時候 result 我們的32個bit的result就是等於0 當zero 這個bit為0的時候 32個bit的result不全為0

實際的應用: 像Branch equal

把兩個暫存器的值拿來比較一下
如果它們相等的話 就要把program counter的值設成label

如何比較兩個暫存器的值是相等的呢?

把它們拿來做減法
當減法的結果result全為0的時候
只要透過判斷zero這個bit
當result全為0 zero就會為1

因此可以很輕易的知道到底這兩個暫存器的值是相等還是不相等

ALU zero 實現

把ALU裡面所有bit的output通通nor在一起

nor gate:

當裡面有任何一個人不為0 也就是任何一個人為1
它的output就會為0

set on less than

slt它是一個R-format的指令

是把Rs暫存器以及Rt暫存器的值拿來比較一下(做減法)
如果Rs暫存器的值小於Rt 那麼我們讓Rd暫存器的值為1
反之 就讓Rd暫存器的值為0

看 $rd

因為暫存器裡面是由32個bit所組合而成
0實際上是代表了我們總共有32個0
1代表的是我們前面有31個0 而最後一個bit為1

這個運算在高位元的31個bit其實都是一模一樣的，通通為0

set on less than 實現

分三個Part討論

bit1~bit30
bit31

• bit 1 ~ bit 30

先看最簡單的部分bit1~bit30
也就是次低位元到次高位元

因為它的output值是0
就把0接到MUX 讓它可以選出來 接出來 收工

• bit 31

其實大家也知道 我們要的output還是0
這樣子就收工了嗎 當然還沒

不要忘了我們要做的是set on less than 我們要比大小

把兩個暫存器的值拿來相減
看它減完的結果是正的還是負的

例如

我們把Rs暫存器減掉Rt 減完的結果我們發現它的值是負的
意思是說它的值小於0

表示Rs暫存器是真的小於Rt的
透過這個結果 我們會知道最後Rd暫存器它必須要等於1

那這個1哪裡來?

最簡單的方法其實就是我們把全部做減法

減完了之後我們發現最高位元減完的結果是1
那這個1剛剛好
因為代表的是Rs減掉Rt的結果是一個負的值
既然是負的值
Rd剛好要1 我們缺了個1
我們就利用這個最高位元的1拿來用就好

結果

最高位元實際上output出來的值仍然是0
可是我們要把最高位元整個減法減完的結果(取名叫做set)
看它是0還是1來判斷減完的結果是正的還是負的

而這個set將來會拿來接到最低位元去

如果set為1

那麼就代表的意思是Rs小於Rt 自然而然將來這個1就接到Rd
也就是接到我們的最低位元就好了(因為1==000...0001)

如果set的值為0

那麼代表的意思就是Rs減掉Rt的值並沒有小於0
那麼我們的Rd的值就不能是1 就要是0
剛好set的值是0 把它接回去就對了  

• bit 0

  

利用剛才整個減法結果set接過來 output出來於是set on less than似乎就完成了

請問這樣真的就把set on less than完成了嗎? 同學們可以想想看。